public class Solution {
    /*  
        问题1：为什么慢指针一圈走不完也能和快指针相遇?
            当low进入环的入口时，fast在环中，假设距离x，fast和low的距离每秒都会减1，知道x秒后相遇，而x<=n，所以low无法走完一圈

        解析1：
            假设起点到环的入口长度为m，环的周长为c；
            相遇时low走了n步，fast点走了2n步；
            fast比low点多走了n步，这n步用来绕着环走，则有 n%c=0
            然后相交点所在位置距离环入口为 n-m，再走m步， n-m+m = n
            即再走m步，low点到入口的距离为n，而n是c的倍数，即low点回到了环入口





        假设low点走过的路程为a+b,fast点走过的距离为a+(b+c)*n+b
        易知fast走过的路程是low的两倍，得到等式： 
        2a+2b = a+(n+1)b+c
     => a = (n-1)(b+c) + c
        所以，如果两个点相遇后，low点移到初始位置，fast在他们相遇的位置
        让他们再走同样的步数a（c），他们还会相与
    */
    public ListNode detectCycle(ListNode head) {
        ListNode link = hasCycle(head);
        if( link==null )
            return null;
        // link为他们的交点
        while( link != head ){
            link = link.next;
            head = head.next;
        }
        return link;
    }
    // 返回他们相遇的点 或 null
    public ListNode hasCycle(ListNode head) {
        ListNode low = head, fast = head;
        while( fast!=null && fast.next!=null ){
            low = low.next;
            fast = fast.next.next;
            if( low==fast )
                return low;
        }
        return null;
    }
}